<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>专题模板 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/61.6dd12daf.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>专题模板</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_01-哨兵" class="sidebar-link">01.哨兵</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_02-数组和链表专题" class="sidebar-link">02.数组和链表专题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_2-1-数组和链表专题" class="sidebar-link">2.1.数组和链表专题</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_2-2-指针的题目" class="sidebar-link">2.2.指针的题目</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_2-3-链表的常见技巧" class="sidebar-link">2.3.链表的常见技巧</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_03-树专题" class="sidebar-link">03.树专题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#树—常考题型之一" class="sidebar-link">树—常考题型之一</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_3-1关于递归到底好不好？" class="sidebar-link">3.1关于递归到底好不好？</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_3-2-树的层序遍历（bfs）" class="sidebar-link">3.2.树的层序遍历（BFS）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_3-3-树的三大遍历" class="sidebar-link">3.3.树的三大遍历</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_3-4-重建二叉树『模板』" class="sidebar-link">3.4.重建二叉树『模板』</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_04-『贪心』解决过桥问题" class="sidebar-link">04.『贪心』解决过桥问题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_4-1-题面" class="sidebar-link">4.1.题面</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_4-2-解法" class="sidebar-link">4.2.解法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_3、结合两种贪心策略的最终代码" class="sidebar-link">3、结合两种贪心策略的最终代码</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_05-『分治』算法" class="sidebar-link">05.『分治』算法</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_06-面试—字符串" class="sidebar-link">06.面试—字符串</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part02.%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%E6%8A%80%E5%B7%A7.html#_07-kmp算法" class="sidebar-link">07.KMP算法</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="专题模板"><a href="#专题模板" class="header-anchor">#</a> 专题模板</h1> <p>⭐️01.哨兵
⭐️02.数组和链表专题
⭐️03.树专题
⭐️04.『贪心』解决过桥问题
⭐️05.『分治』算法</p> <h2 id="_01-哨兵"><a href="#_01-哨兵" class="header-anchor">#</a> 01.哨兵</h2> <ul><li>参考<a href="https://blog.csdn.net/w453908766/article/details/50916790" target="_blank" rel="noopener noreferrer">CSDN<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li><code>sentry</code>，哨兵</li> <li>哨兵，顾名思义，是用来解决国家之间<strong>边界问题</strong>的，不直接参与生产活动。</li> <li>同样，计算机科学中提到的哨兵，也用来解决边界问题。<br> <code>A sentinel is a dummy object that allows us to simplify boundary conditions.</code>
哨兵是用来简化边界问题的虚设对象<br>
比如：我们在判断链表是否为空，加不加一个头结点，就能看见代码的改善与否。</li></ul> <h2 id="_02-数组和链表专题"><a href="#_02-数组和链表专题" class="header-anchor">#</a> 02.数组和链表专题</h2> <h3 id="_2-1-数组和链表专题"><a href="#_2-1-数组和链表专题" class="header-anchor">#</a> 2.1.数组和链表专题</h3> <p>排序数组中的搜索问题，首先想到 二分法 解决。</p> <p>排序数组使用双指针也是高频选项</p> <h3 id="_2-2-指针的题目"><a href="#_2-2-指针的题目" class="header-anchor">#</a> 2.2.指针的题目</h3> <ul><li>1）首先记得想，会不会是NULL（顺路也考虑了程序的健壮性）</li> <li>2）指针的题目，就是不断的移动指针达到题目要求</li></ul> <h3 id="_2-3-链表的常见技巧"><a href="#_2-3-链表的常见技巧" class="header-anchor">#</a> 2.3.链表的常见技巧</h3> <h2 id="_03-树专题"><a href="#_03-树专题" class="header-anchor">#</a> 03.树专题</h2> <p>树和链表都是递归结构，很多树的问题可以使用递归来处理。</p> <p>几种遍历，</p> <p>其中，主要考察，我们对递归的实现？</p> <p>但是其实有非递归的实现，（面试可能考！！！）</p> <h3 id="树—常考题型之一"><a href="#树—常考题型之一" class="header-anchor">#</a> 树—常考题型之一</h3> <ul><li><a href="https://www.nowcoder.com/questionTerminal/cafc86b72f2c42b8aacb47178b045026" target="_blank" rel="noopener noreferrer">完全二叉树<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>共有700结点，该二叉树有多少个叶子结点？</li></ul> <h3 id="_3-1关于递归到底好不好？"><a href="#_3-1关于递归到底好不好？" class="header-anchor">#</a> 3.1关于递归到底好不好？</h3> <ul><li>可能以前在做ACM题目的时候，个人对递归有偏见</li> <li>但是面试以来，递归是很好的，它能保证递归有足够的空间去，一般不会爆栈！！！！</li> <li>此外面试的时候是有时间控制的，你需要做的是『精简代码、快速解答』</li> <li>110平衡二叉树+剑指offer55
借助做过的求树的高度的题目进行递归
其实自己都不知道为什么AC了，但是获得了经验</li></ul> <p>1、递归不一定只是递归本身。可以几个不同函数一起递归，分解问题</p> <h3 id="_3-2-树的层序遍历（bfs）"><a href="#_3-2-树的层序遍历（bfs）" class="header-anchor">#</a> 3.2.树的层序遍历（BFS）</h3> <p>牛客上，没有return最终结果，竟然还能出现内存超限的情况。。。</p> <p>我在LeetCode上，有用过两个vector模拟队列，但是在这，我用len控制了遍历的节点数。
就能只用一个队列。</p> <h3 id="_3-3-树的三大遍历"><a href="#_3-3-树的三大遍历" class="header-anchor">#</a> 3.3.树的三大遍历</h3> <h4 id="_3-3-1-递归写法"><a href="#_3-3-1-递归写法" class="header-anchor">#</a> 3.3.1.递归写法</h4> <ul><li>递归写法（习惯递归这种技巧，强化）
前序、中序、后序遍历，一套框架（伪代码）</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">DFS</span><span class="token punctuation">(</span> TreeNode <span class="token operator">*</span> root <span class="token punctuation">)</span>
<span class="token punctuation">{</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//前序遍历visit</span>
    <span class="token function">DFS</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>left <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//中序遍历visit</span>
    <span class="token function">DFS</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>right <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//后序遍历visit</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><h4 id="_3-3-2-栈模拟写法（非递归）"><a href="#_3-3-2-栈模拟写法（非递归）" class="header-anchor">#</a> 3.3.2.栈模拟写法（非递归）</h4> <ul><li>非递归写法一（重点掌握，防止爆内存栈）——借助栈实现</li></ul> <h4 id="_1、前序遍历"><a href="#_1、前序遍历" class="header-anchor">#</a> 1、前序遍历</h4> <p>原理：
根-》左-》右
变为
先访问根</p> <p>stack先入右边，后入左边，这样，出栈遍历就OK</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">preorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
        
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span><span class="token comment">//返回值</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    stack<span class="token operator">&lt;</span>TreeNode <span class="token operator">*</span><span class="token operator">&gt;</span> st<span class="token punctuation">;</span>
    st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> root <span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>st<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        TreeNode <span class="token operator">*</span> temp<span class="token operator">=</span>st<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>temp <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//先访问根节点val</span>

        <span class="token comment">//下面是核心代码：先右后左，这样就能在出栈的时候保证，左子树先被遍历</span>
        st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>right <span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>left <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><h4 id="_2、后序遍历"><a href="#_2、后序遍历" class="header-anchor">#</a> 2、后序遍历</h4> <p>原理：借鉴了前序的，想办法，将两者的写法尽量统一！
前序遍历为root-&gt;left-&gt;right
后序遍历为left-&gt;right-&gt;root
我们如果可以修改前序遍历为root-&gt;right-&gt;left
显然就可以用STL的reverse算法反转就OK了</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">postorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> 
<span class="token punctuation">{</span>

    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    stack<span class="token operator">&lt;</span>TreeNode <span class="token operator">*</span> <span class="token operator">&gt;</span> st<span class="token punctuation">;</span>
    st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>st<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        TreeNode <span class="token operator">*</span> temp<span class="token operator">=</span>st<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>temp <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>left <span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>right <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//反转</span>
    <span class="token function">reverse</span><span class="token punctuation">(</span> ret<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> ret<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><h4 id="_3、中序遍历"><a href="#_3、中序遍历" class="header-anchor">#</a> 3、中序遍历</h4> <ul><li>1、这个的理解和前面两个不一样，这个需要借助DFS的角度来看</li> <li>2、可以借助《算法笔记》中DFS走迷宫来理解代码。</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">inorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span> <span class="token operator">==</span> root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    stack<span class="token operator">&lt;</span>TreeNode <span class="token operator">*</span> <span class="token operator">&gt;</span> st<span class="token punctuation">;</span>

    TreeNode <span class="token operator">*</span> cur<span class="token operator">=</span>root<span class="token punctuation">;</span>
    <span class="token comment">//注意是或</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>cur <span class="token operator">||</span> <span class="token punctuation">(</span><span class="token operator">!</span>st<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//DFS之一条路走到最左的</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>cur <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> cur <span class="token punctuation">)</span><span class="token punctuation">;</span>
            cur<span class="token operator">=</span>cur<span class="token operator">-&gt;</span>left<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        TreeNode <span class="token operator">*</span> temp<span class="token operator">=</span>st<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//放入输出的数组</span>
        <span class="token comment">//注意是变成temp的右边</span>
        cur<span class="token operator">=</span> temp<span class="token operator">-&gt;</span>right<span class="token punctuation">;</span><span class="token comment">//开始到当前节点的右边去遍历，如果没有，显然会先经过根</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><h4 id="_3-3-3-morris遍历、化树为链表（非递归）"><a href="#_3-3-3-morris遍历、化树为链表（非递归）" class="header-anchor">#</a> 3.3.3.Morris遍历、化树为链表（非递归）</h4> <h4 id="_1、中序遍历"><a href="#_1、中序遍历" class="header-anchor">#</a> 1、中序遍历</h4> <p>特点，改变了二叉树结构，将二叉树变成了“链表”</p> <ul><li>时间复杂度：$O(n)$ $O(n)$，其中 nn 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)$=$O(n)$$O(2n)$=$O(n)$。</li> <li>空间复杂度：$O(1)$ $O(1)$。</li></ul> <p>讲解：
<a href="https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/dong-hua-yan-shi-94-er-cha-shu-de-zhong-xu-bian-li/" target="_blank" rel="noopener noreferrer">1、Leecode动画演示<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <p>2、讲解算法</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>思路与算法
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><ul><li>代码</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">inorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> rt<span class="token punctuation">;</span>
    TreeNode <span class="token operator">*</span> preNode<span class="token operator">=</span><span class="token keyword">nullptr</span><span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//1.链表的左边，要先遍历的</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span><span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>left<span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//（1）第1步，preNode节点就是当前 root 节点向左走一步，</span>
            <span class="token comment">//然后一直向右走至无法走为止（理解）</span>
            preNode<span class="token operator">=</span>root<span class="token operator">-&gt;</span>left<span class="token punctuation">;</span>

            <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span> <span class="token punctuation">(</span>preNode<span class="token operator">-&gt;</span>right<span class="token punctuation">)</span>  <span class="token operator">&amp;&amp;</span> <span class="token punctuation">(</span>preNode<span class="token operator">-&gt;</span>right<span class="token punctuation">)</span> <span class="token operator">!=</span> root <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                preNode<span class="token operator">=</span>preNode<span class="token operator">-&gt;</span>right<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>


            <span class="token comment">//（2）第2步，如果，这个preNode的右边节点是nullptr</span>
            <span class="token comment">//显然我还没有改变成链表</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span><span class="token punctuation">(</span>preNode<span class="token operator">-&gt;</span>right<span class="token punctuation">)</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//改变为“链表”</span>
                preNode<span class="token operator">-&gt;</span>right<span class="token operator">=</span>root<span class="token punctuation">;</span>
                <span class="token comment">//局部改变之后，我们移动root，准备下一次的改变成链表</span>
                root<span class="token operator">=</span>root<span class="token operator">-&gt;</span>left<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//（2）第2步，如果，preNode-&gt;right == root</span>
                <span class="token comment">//说明左子树已经访问完了，我们可以直接开始遍历了</span>
                <span class="token comment">//此外我们需要断开链接？？</span>
                rt<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span>
                preNode<span class="token operator">-&gt;</span>right<span class="token operator">=</span><span class="token keyword">nullptr</span><span class="token punctuation">;</span><span class="token comment">//断开？？？这步需要吗？</span>
                root<span class="token operator">=</span>root<span class="token operator">-&gt;</span>right<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>


        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//2.没有左孩子，则直接访问右孩子</span>
            rt<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span>
            root<span class="token operator">=</span>root<span class="token operator">-&gt;</span>right<span class="token punctuation">;</span><span class="token comment">//不断看被改成的链表右侧</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>   

    <span class="token keyword">return</span> rt<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br></div></div><h4 id="_3-3-4-线索化二叉树（非递归）"><a href="#_3-3-4-线索化二叉树（非递归）" class="header-anchor">#</a> 3.3.4.线索化二叉树（非递归）</h4> <p>实际做OJ的时候，这种解法可能有局限，毕竟要修改结构体。
新增两个指针。</p> <h3 id="_3-4-重建二叉树『模板』"><a href="#_3-4-重建二叉树『模板』" class="header-anchor">#</a> 3.4.重建二叉树『模板』</h3> <h4 id="_3-4-1-需要熟练的树的代码"><a href="#_3-4-1-需要熟练的树的代码" class="header-anchor">#</a> 3.4.1.需要熟练的树的代码</h4> <ul><li>效果：手到码出</li> <li>递归：前、中、后序遍历</li> <li>迭代：前、中、后序遍历</li></ul> <h4 id="_3-4-2-重建二叉树『模板』"><a href="#_3-4-2-重建二叉树『模板』" class="header-anchor">#</a> 3.4.2.重建二叉树『模板』</h4> <blockquote><p>有2个新名词：</p></blockquote> <ul><li>1、序列化：必须保存1个中序遍历的结果，然后外加1个前序or后序遍历的结果</li> <li>2、反序列化：根据2次遍历生成的结果恢复二叉树</li></ul> <h4 id="_1、中序-前序-二叉树『树无重复元素』"><a href="#_1、中序-前序-二叉树『树无重复元素』" class="header-anchor">#</a> 1、中序+前序-&gt;二叉树『树无重复元素』</h4> <ul><li><a href="https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/" target="_blank" rel="noopener noreferrer">105. 从前序与中序遍历序列构造二叉树<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li><a href="https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/" target="_blank" rel="noopener noreferrer">剑指 Offer 07. 重建二叉树<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h4 id="（1）递归模板"><a href="#（1）递归模板" class="header-anchor">#</a> （1）递归模板</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */</span>

TreeNode <span class="token operator">*</span> <span class="token function">solve</span>
<span class="token punctuation">(</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator preBegin<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator preEnd<span class="token punctuation">,</span> 
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator inBegin<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator inEnd 
<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> preBegin<span class="token operator">==</span>preEnd <span class="token operator">||</span> inBegin<span class="token operator">==</span>inEnd <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    TreeNode <span class="token operator">*</span> root<span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">TreeNode</span><span class="token punctuation">(</span> <span class="token operator">*</span>preBegin <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//不记得下面这个函数，也可以用for循环自行查找。</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator it<span class="token operator">=</span> <span class="token function">find</span><span class="token punctuation">(</span> inBegin<span class="token punctuation">,</span> inEnd<span class="token punctuation">,</span> root<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> num<span class="token operator">=</span><span class="token punctuation">(</span>it<span class="token operator">-</span>inBegin<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment">//递归，左闭右开『注意事项』</span>
    root<span class="token operator">-&gt;</span>left<span class="token operator">=</span><span class="token function">solve</span><span class="token punctuation">(</span> preBegin<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> preBegin<span class="token operator">+</span><span class="token number">1</span><span class="token operator">+</span>num<span class="token punctuation">,</span> inBegin<span class="token punctuation">,</span>inBegin<span class="token operator">+</span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    root<span class="token operator">-&gt;</span>right<span class="token operator">=</span><span class="token function">solve</span><span class="token punctuation">(</span> preBegin<span class="token operator">+</span><span class="token number">1</span><span class="token operator">+</span>num<span class="token punctuation">,</span> preEnd<span class="token punctuation">,</span> inBegin<span class="token operator">+</span>num<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> inEnd<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> root<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    TreeNode<span class="token operator">*</span> <span class="token function">buildTree</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> preorder<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> inorder<span class="token punctuation">)</span> 
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token function">solve</span>
        <span class="token punctuation">(</span> 
            preorder<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">,</span> preorder<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">,</span> 
            inorder<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">,</span> inorder<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br></div></div><h4 id="_2、中序-后序-二叉树『树无重复元素』"><a href="#_2、中序-后序-二叉树『树无重复元素』" class="header-anchor">#</a> 2、中序+后序-&gt;二叉树『树无重复元素』</h4> <ul><li><a href="https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/" target="_blank" rel="noopener noreferrer">106. 从中序与后序遍历序列构造二叉树<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>PTA甲级<a href="https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072" target="_blank" rel="noopener noreferrer">1020 Tree Traversals<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h4 id="（1）递归模板-2"><a href="#（1）递归模板-2" class="header-anchor">#</a> （1）递归模板</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>
TreeNode <span class="token operator">*</span> <span class="token function">solve</span>
<span class="token punctuation">(</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator inBegin<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator inEnd<span class="token punctuation">,</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator postBegin<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator postEnd
<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> inBegin<span class="token operator">==</span>inEnd <span class="token operator">||</span> postBegin<span class="token operator">==</span>postEnd <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    TreeNode <span class="token operator">*</span> root<span class="token operator">=</span><span class="token keyword">new</span> <span class="token function">TreeNode</span><span class="token punctuation">(</span> <span class="token operator">*</span><span class="token punctuation">(</span>postEnd<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator it<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span> it<span class="token operator">=</span>inBegin<span class="token punctuation">;</span> it<span class="token operator">&lt;</span>inEnd<span class="token punctuation">;</span> <span class="token operator">++</span>it<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token operator">*</span>it<span class="token operator">==</span>root<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
	<span class="token comment">//注意：左闭右开</span>
    <span class="token keyword">int</span> num<span class="token operator">=</span>it<span class="token operator">-</span>inBegin<span class="token punctuation">;</span>
    root<span class="token operator">-&gt;</span>left<span class="token operator">=</span><span class="token function">solve</span><span class="token punctuation">(</span> inBegin<span class="token punctuation">,</span> inBegin<span class="token operator">+</span>num<span class="token punctuation">,</span> postBegin<span class="token punctuation">,</span> postBegin<span class="token operator">+</span>num <span class="token punctuation">)</span><span class="token punctuation">;</span>
    root<span class="token operator">-&gt;</span>right<span class="token operator">=</span><span class="token function">solve</span><span class="token punctuation">(</span> inBegin<span class="token operator">+</span>num<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> inEnd<span class="token punctuation">,</span> postBegin<span class="token operator">+</span>num<span class="token punctuation">,</span> postEnd<span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> root<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    TreeNode<span class="token operator">*</span> <span class="token function">buildTree</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> inorder<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> postorder<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">return</span> <span class="token function">solve</span><span class="token punctuation">(</span> inorder<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> inorder<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> postorder<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> postorder<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br></div></div><h4 id="_3、中序-层序-二叉树"><a href="#_3、中序-层序-二叉树" class="header-anchor">#</a> 3、中序+层序-&gt;二叉树</h4> <ul><li>这个结论，是在『算法笔记』上看到的，我们写出下面的模板代码</li> <li>注意：区间的开闭</li></ul> <blockquote><p><a href="https://www.w3xue.com/exp/article/20193/27695.html" target="_blank" rel="noopener noreferrer">参考博客<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></blockquote> <h4 id="_4、前序-后序-二叉树『不唯一』"><a href="#_4、前序-后序-二叉树『不唯一』" class="header-anchor">#</a> 4、前序+后序-&gt;二叉树『不唯一』</h4> <p>（显然树不唯一）</p> <p><a href="https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/" target="_blank" rel="noopener noreferrer">889. 根据前序和后序遍历构造二叉树<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <h2 id="_04-『贪心』解决过桥问题"><a href="#_04-『贪心』解决过桥问题" class="header-anchor">#</a> 04.『贪心』解决过桥问题</h2> <h3 id="_4-1-题面"><a href="#_4-1-题面" class="header-anchor">#</a> 4.1.题面</h3> <ul><li>N个人在晚上想通过桥。每次最多过去2个人，需要有手电筒。现在只有1个手电筒。每个人过桥的速度都不一样，过桥的时间以慢的为准。你的工作是找到最少的过桥的方法;</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>  输入:
  首先是n,然后n行是过桥的时间。
  人数不超过1000，而且没有人过桥的时间超过100秒;
  输出:
  首先输出总共所需最少时间;下面表示过桥的过程(见样例)，如果有多种过桥方案，输出其中一种。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><ul><li>来源：IBM面试题，一道标准的贪心题目</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>样例输入：
输入样例
4 	//4个人
1
2
5
10
样例输出：
输出样例
17
1 2			//1和2先过去
1			//1回来
5 10		//5和10过去
2			//2回来
1 2		    //1 2 过去
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><h3 id="_4-2-解法"><a href="#_4-2-解法" class="header-anchor">#</a> 4.2.解法</h3> <p>算法复杂度在于排序</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>样例：
<span class="token number">4</span>
<span class="token number">1</span> <span class="token number">2</span> <span class="token number">5</span> <span class="token number">10</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h4 id="_1）贪心第1部分——贪心策略1（表述不如，算法清晰）"><a href="#_1）贪心第1部分——贪心策略1（表述不如，算法清晰）" class="header-anchor">#</a> 1）贪心第1部分——贪心策略1（表述不如，算法清晰）</h4> <ul><li>1）每次过桥2个人， <s>希望一起过去的人时间相差最小</s> ，选领近的两个，所以采用贪心技术。（第1个要贪心的）</li> <li>理解：比如，上面的最大的10是肯定没有办法避免的，但是我就希望这个5就不要在出现在我的和式里面了
时间相差最小：比如，时间最多的人和时间次多的人一起过，这样我们最大的那个时间10就只出现一次
怎么办？所以，我希望在过桥的时候，是5和10一起过</li> <li>2）而且返回的时间要少，所以用时间最少的人返回;往回送手电筒的人，时间要少（第2个贪心）</li></ul> <h4 id="_2）贪心策略1的算法："><a href="#_2）贪心策略1的算法：" class="header-anchor">#</a> 2）贪心策略1的算法：</h4> <p>预处理：我们将过桥的时间从小到大排好序，标记为T1,T2,T3..Tn</p> <blockquote><ul><li>1.首先让时间最少的两人过去，T1，T2（这2个人的使命是：用来往回送手电筒的）</li> <li>2.然后，返回T1和T2中的哪一个呢？
-- Q：难道返回任何一个都没有关系？
-- A：T1不是这次返回的话，反正下次还是要返回的
但是，请看这个样例：如果只有3个人，1 2 3，显然如果要T2回去送，返回的时候会长一点点，会影响时间</li> <li>3.让Tn和Tn-1一起过去，我们希望在时间的总和里面，Tn出现，但是比他稍微小一点的Tn-1就不用再出现了</li> <li>4.然后余下的T2返回</li></ul></blockquote> <p>显然，观察容易知道，经过以上4个步骤会出现：
T1和T2又回到了最初的位置，Tn和Tn-1却过河了
这样，我们就从n个人转换为了n-2个人过河
来回2趟，送过去2个人，得到一个部分最优解。
在这个基础上，不断的分解</p> <h4 id="_3）贪心第2部分——贪心策略2"><a href="#_3）贪心第2部分——贪心策略2" class="header-anchor">#</a> 3）贪心第2部分——贪心策略2</h4> <p>Q：先前的策略是，时间最小的2个人来送手电筒，那么能否只让时间最小的1个人来送手电筒？
A：不能，因为从数学上可以证明</p> <p>显然，我们上面的样例中，那个时间5会加到我们的总和中去，</p> <p>广义的数学证明这个贪心策略不行：</p> <p>抽象从小到大的4个数，T1，T2，Tn-1，Tn</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>贪心策略1：
比如，Tn-1不会出现在最终和式中
T1 T2过去 （T2）
T1回来		（T1）
Tn-1和Tn过去	（Tn)
T2回来		(T2)
sum1=Tn+2*T2+T1;

贪心策略2：
Tn,Tn-1啥的都会出现在最终和式
T1 Tn过去  （Tn）
T1回来		（T1）
T1和Tn-1过去	（Tn-1)
T1回来		(T1)
sum2=Tn+T（n-1）1+2*T1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><p>显然
sum2-sum1&lt;0的时候，需要满足Tn-1&lt; 2*T2-T1才能使用
比如这个样例</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>4
1 4 5 10
贪心策略1：
10+2*4+1=19
贪心策略2：
10+5+2*1=17
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p>所以，我们使用贪心策略1还是2的时候，需要判别Tn-1&lt; 2*T2-T1的成立与否</p> <h3 id="_3、结合两种贪心策略的最终代码"><a href="#_3、结合两种贪心策略的最终代码" class="header-anchor">#</a> 3、结合两种贪心策略的最终代码</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">1000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> test<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token punctuation">;</span>




<span class="token comment">//伪代码，时间复杂度是O（n）</span>
<span class="token keyword">void</span> <span class="token function">solve</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>

	<span class="token comment">//t表示的意识是</span>
	t<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>T2<span class="token operator">-</span> T1 （最小的T1，次小的T2）

	<span class="token comment">//2个人来回送手电筒贪心策略</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>n<span class="token operator">-</span>l<span class="token punctuation">;</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator">-</span>l<span class="token punctuation">]</span><span class="token operator">&gt;</span>t<span class="token punctuation">)</span><span class="token operator">&amp;</span><span class="token punctuation">(</span>i<span class="token operator">&gt;</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">;</span>i<span class="token operator">-=</span><span class="token number">2</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d %d\n&quot;</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d %d\n&quot;</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token comment">//Tn-1&lt; 2*T2-T1才能使用</span>
	<span class="token comment">//1个人来回送手电筒贪心策略</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token punctuation">;</span> j<span class="token operator">&gt;</span>l <span class="token punctuation">;</span> <span class="token operator">--</span>j<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d %d\n&quot;</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>



<span class="token comment">//真实代码</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> n<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>test<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>

		<span class="token function">sort</span><span class="token punctuation">(</span>test<span class="token punctuation">,</span>test<span class="token operator">+</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//将所有的时间排序是贪心法的预备工作</span>

	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>



</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br></div></div><h2 id="_05-『分治』算法"><a href="#_05-『分治』算法" class="header-anchor">#</a> 05.『分治』算法</h2> <blockquote><p>很显然，递归这种『编码技巧』，就是分治算法的完美体现之一</p></blockquote> <p><strong>1、使用情况</strong></p> <p>问题规模比较大的时候，难以求解
想办法减少</p> <p><code>贪心，DP，分治，减治</code>
减治，由于时间的关系，我们就不举例子了。</p> <p>分治：
我们用得比较多的也是二分法，或者三分法</p> <p><strong>2、分治法-到底如何分解问题</strong></p> <p>到底如何分解问题，其实我一直很迷惑，9.2号。我突然想到一个好像不错的方法：</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>1）找到最大的问题
2）找到最简化的问题（最小的问题）
3）分析如何从最大的问题一步步转换为最小的问题
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p>我后面，自己找了一个3人，3鬼的方法验证<br>
3人3鬼过河，人的数目要比鬼多，否则鬼会吃掉人</p> <p><strong>3、最大问题</strong></p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人人人 鬼鬼鬼|  |
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p><strong>4、最小问题</strong></p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人 鬼|	|
这个容易解决，一次性过去。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>5、中等问题</strong></p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人人鬼鬼| |
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p>显然，中等问题要成功，最后的状态要是</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人鬼|  |人鬼
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p>或者</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>鬼| |人人鬼
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p><strong>转换关系</strong></p> <p>最大要转换为</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人人鬼鬼|（船在这）  |人鬼
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p>中等问题要转换为</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>人鬼|（船在这） |人鬼
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><h2 id="_06-面试—字符串"><a href="#_06-面试—字符串" class="header-anchor">#</a> 06.面试—字符串</h2> <ul><li>参考文章：<a href="https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/yi-ge-mo-ban-shua-bian-suo-you-zi-fu-chu-x6vh/" target="_blank" rel="noopener noreferrer">一个模板刷遍所有字符串句子题目<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>！（归纳总结+分类模板+题目分析）
<ul><li>注意点：字符串的遍历，记得“擦屁股”—也就是收拾最后的残局</li></ul></li></ul> <h2 id="_07-kmp算法"><a href="#_07-kmp算法" class="header-anchor">#</a> 07.KMP算法</h2> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>


<span class="token keyword">class</span> <span class="token class-name">KMP</span>
<span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">void</span> <span class="token function">getNext</span><span class="token punctuation">(</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&amp;</span> next<span class="token punctuation">,</span> string s <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//我的理解，getNext其实本质也是个strStr的函数，</span>
        <span class="token comment">//其中，文本串是『后缀XXX』，needle__也就是s是『前缀XXX』</span>

        <span class="token keyword">int</span> prefixPos<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//初始化『前缀末尾位置』</span>
        next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//初始化next[0]的回退位置</span>

        <span class="token comment">//i意义1：表示『后缀末尾的位置』,初始化next[i]</span>
        <span class="token comment">//意义2：此外，i还代表当前XXX</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> suffixPos <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> suffixPos <span class="token operator">&lt;</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>suffixPos<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>

            <span class="token comment">//易错，不能是if，因为可能借助next多次回退</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> prefixPos<span class="token operator">&gt;</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> s<span class="token punctuation">[</span>prefixPos<span class="token punctuation">]</span><span class="token operator">!=</span>s<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                prefixPos<span class="token operator">=</span>next<span class="token punctuation">[</span>prefixPos<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span> s<span class="token punctuation">[</span>prefixPos<span class="token punctuation">]</span><span class="token operator">==</span>s<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>prefixPos<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//初始化next</span>
            next<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span><span class="token operator">=</span>prefixPos<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>


    <span class="token keyword">int</span> <span class="token function">strStr</span><span class="token punctuation">(</span> string haystack<span class="token punctuation">,</span> string needle <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token operator">==</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">next</span><span class="token punctuation">(</span> needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">getNext</span><span class="token punctuation">(</span> next<span class="token punctuation">,</span> needle <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//needle串，当前需要测试匹配性的位置</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>haystack<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//易错：不能用if，因为可能多次借助next数组回退</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> j<span class="token operator">&gt;</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span>needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                j<span class="token operator">=</span>next<span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//如果匹配了1个字符，显然会后移</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>j<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//完全匹配</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j<span class="token operator">==</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//注意，因为i还来不及+1，所以，返回前要+1然后才能减掉</span>
                <span class="token keyword">return</span> <span class="token punctuation">(</span> i<span class="token operator">+</span><span class="token number">1</span><span class="token operator">-</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//匹配失败</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br></div></div></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/61.6dd12daf.js" defer></script>
  </body>
</html>
